Hypergraph / Acyclic subhypergraph (Bibtex)

P40: Enumeration of all maximal $\alpha$-acyclic subhypergraphs in a hypergraph

Input:

A hypergraph $H = (V, \mathcal{E})$.

Output:

All maximal $\alpha$-acyclic subhypergraphs in $H$.

Complexity:

$O(|\mathcal{E}|^2(|V|+|\mathcal{E}|))$ delay and $O(|\mathcal{E}|)$space.

Comment:

The name of their algorithm is $\mathtt{GenMAS}$. This algorithm uses the algorithm $\mathtt{FindMAS}$ that outputs a maximal $\alpha$-acyclic subhypergraph.

Reference:

[Daigo2009] (Bibtex)

P176: Enumeration of all Berge acyclic subhypergraphs in a hypergraph

Input:

A hypergraph $\mathcal{H}$.

Output:

All Berge acyclic subhypergraphs in $\mathcal{H}$.

Complexity:

$O(rd\tau(m))$ time per subhypergraph.

Comment:

$r$ and $d$ are the rank and the degree of $\mathcal{H}$ and $\tau(m) = O((\log\log m)^2 / \log \log \log (m))$.

Reference:

[Wasa2013] (Bibtex)